package main

import (
	"fmt"
)

/**
 * Definition for a binary tree node.
 *
 */
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func generateTrees(n int) []*TreeNode {
	var pre []*TreeNode
	if n == 0 {
		return pre
	}
	pre = append(pre, nil)
	for i := 1; i <= n; i++ {
		var cur []*TreeNode
		for _, root := range pre {
			// 直接向右插入根节点
			ins := &TreeNode{Val: i}
			ins.Left = root
			cur = append(cur, ins)
			// 插入右子节点
			for j := 0; j <= n; j++ {
				rootCopy := treeCopy(root) // 复制当前树
				right := rootCopy          // 找到要插入的右子位置
				// 找右子
				for k := 0; k < j; k++ {
					if right == nil {
						break
					}
					right = right.Right
				}
				if right == nil { //提前结束
					break
				}
				rightTree := right.Right

				ins = &TreeNode{Val: i}
				right.Right = ins    //右孩子是插入的节点
				ins.Left = rightTree //插入节点的左孩子更新为插入位置之前的子树
				//加入结果中
				cur = append(cur, rootCopy)
			}
		}
		pre = cur
	}
	return pre
}

func treeCopy(root *TreeNode) *TreeNode {
	if root == nil {
		return root
	}
	return &TreeNode{
		Val:   root.Val,
		Left:  treeCopy(root.Left),
		Right: treeCopy(root.Right),
	}
}

func main() {
	t := generateTrees(3)
	for i, v := range t {
		//fmt.Printf("%v \n", v)
		fmt.Printf("%d ->: %d \n", i, v.Val)
	}
}
